export interface TreeNode<T = any> {
    /**
     * 节点唯一标识
     * @example 1
     */
    id: T;

    /**
     * 父节点标识，为 undefined/null 表示根节点
     * @example 0
     */
    pid?: T | null;

    /**
     * 子节点数组
     * @default []
     */
    children?: TreeNode<T>[];

    /**
     * 排序权重
     * @default 0
     */
    sort?: number;

    /**
     * 允许扩展其他属性
     */
    [key: string]: any;
}

export interface BuildTreeOptions<T = any> {
    /**
     * 节点ID字段名
     * @default 'id'
     */
    idKey?: string;

    /**
     * 父节点ID字段名
     * @default 'pid'
     */
    pidKey?: string;

    /**
     * 排序字段名
     * @default 'sort'
     */
    sortKey?: string;

    /**
     * 自定义排序方法
     * @default (a, b) => b.sort - a.sort
     */
    sortComparator?: (a: TreeNode<T>, b: TreeNode<T>) => number;
}

/**
 * 将扁平节点列表转换为树形结构
 * @param items - 扁平节点数组
 * @param options - 配置选项
 * @returns 树形结构根节点数组
 *
 * @description
 * options 配置选项：
 *  - `idKey` 节点唯一标识字段名，默认值为 `'id'`
 *  - `pidKey` 父节点标识字段名，默认值为 `'pid'`
 *  - `sortKey` 排序权重字段名，默认值为 `'sort'`
 *  - `sortComparator` 自定义排序方法，默认值为 `(a, b) => b.sort - a.sort`，即按 `sort` 从大到小排序
 *
 * @example
 * const items = [
 *   { id: 1, name: '部门A', pid: null, sort: 2 },
 *   { id: 2, name: '部门B', pid: 1, sort: 1 },
 *   { id: 3, name: '部门C', pid: 1, sort: 3 }
 * ];
 *
 * const tree = buildTree(items);
 * // 输出结构：
 * // [{
 * //   id: 1, name: '部门A', pid: null, sort: 2,
 * //   children: [
 * //     { id: 3, name: '部门C', pid: 1, sort: 3, children: [] },
 * //     { id: 2, name: '部门B', pid: 1, sort: 1, children: [] }
 * //   ]
 * // }]
 */
export function buildTree<T = any>(items: TreeNode<T>[], options: BuildTreeOptions<T> = {}): TreeNode<T>[] {
    const {
        idKey = "id",
        pidKey = "pid",
        sortKey = "sort",
        sortComparator = (a, b) => (b[sortKey] || 0) - (a[sortKey] || 0)
    } = options;

    // 创建映射表并初始化 children
    const nodeMap = new Map<T, TreeNode<T>>();
    items.forEach(item => {
        nodeMap.set(item[idKey], { ...item, children: [] });
    });

    // 构建树结构
    const roots: TreeNode<T>[] = [];
    nodeMap.forEach(node => {
        const parentId = node[pidKey];

        if (parentId != null && nodeMap.has(parentId)) {
            nodeMap.get(parentId)?.children?.push(node);
        } else {
            roots.push(node);
        }
    });

    // 递归排序函数
    const sortTree = (nodes: TreeNode<T>[]) => {
        nodes.sort(sortComparator);
        nodes.forEach(node => {
            if (node.children?.length) sortTree(node.children);
        });
    };

    sortTree(roots);
    return roots;
}
